import java.util.ArrayList;
import java.util.List;
//51. N 皇后
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        char[][] path = new char[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                path[i][j]='.';
            }
        }
        dfs(ans,path,n,0);
        return ans;
    }
    public void dfs(List<List<String>> ans, char[][] path, int n, int k){
        if(n==k){
            List<String> temp = new ArrayList<>();
            for(int i=0;i<n;i++){
                temp.add(String.valueOf(path[i]));
            }
            ans.add(new ArrayList<>(temp));
            return;
        }
        for(int i = 0;i<n;i++){
            if(isVaild(path,n,k,i)){
                path[k][i] = 'Q';
                dfs(ans,path,n,k+1);
                path[k][i] = '.';
            }
        }

    }
    public boolean isVaild(char[][] path,int n,int x,int y){
        if(x==0){
            return true;
        }
        for(int i=0;i<x;i++){  // 列
            if(path[i][y]=='Q'){
                return false;
            }
        }
        int a = x,b = y;
        while(a>=0&&b>=0){ // 左上角
            if(path[a--][b--]=='Q'){
                return false;
            }
        }
        a = x;
        b = y;
        while(a>=0&&b<n){ // 右上角
            if(path[a--][b++]=='Q'){
                return false;
            }
        }
        return true;
    }
}